// 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

// 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

// 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

// 示例 1:

// 输入: [3,2,1,5,6,4], k = 2
// 输出: 5
// 示例 2:

// 输入: [3,2,3,1,2,4,5,5,6], k = 4
// 输出: 4

// 第k个最大元素 相当于  降序 排序好的第 k- 1个 下标
// 快排 应用
// 确定好 定义 k <= nums.length 的
findKthLargest = function (nums, k) {
  const quicksort = (l, r) => {
    const ol = l,
      or = r
    const pivot = nums[Math.floor((l + r) / 2)] // 选择基准值
    // p 为 pivot 的下标
    while (l <= r) {
      while (nums[l] > pivot) l++ // 找到一个 小于等于 pivot 的
      while (nums[r] < pivot) r-- // 找比 一个 大于等于 pivot 的
      if (l <= r) {
        ;[nums[l], nums[r]] = [nums[r], nums[l]] // 互相交换位置！
        l++
        r--
      }
    } // 这样一圈下来   Math.floor((l + r) / 2) 左边的都比 pivot 大  右边都比pivot 小
    // 注意这里是 大的在左边 小的在右边   而且  最后的 下标 规律 一定是 p = r+1 p = l  -1; 因为 最后 l r 都移动到 p 位置 然后 pivot 和自己交换 l++ r--

    // 判断是否找到第 k个 大元素
    // 找到个 k大元素 所在 区间
    // k -1 代表 k个大元素的下标
    // 第k个最大元素 相当于  降序 排序好的第 k- 1个 下标
    //当 k-1 小于等于 r 了 一定在左边了 因为 是第k个最最大元素
    // // 确定好 定义 k <= nums.length 的
    if (k - 1 >= ol && k - 1 <= r) {
      // 在 左区间 即 比 pivot 大些的区间
      // k - 1 <= r 都比这小了 说明 即使有重复 也会在这个区间里 因为 r+1 = p p 左边的都比p大
      //  r p l 这是 下标顺序
      return quicksort(ol, r)
    }

    // 这样当k-1 都比 l要大了 那一一定 就是在右区间
    if (k - 1 >= l && k - 1 <= or) {
      // 在右区间即 比 pivot 小些的区间
      return quicksort(l, or)
    }

    // 第K大 就是 pivot 了  因为在左区间 找不到 再右区间也找不到 那就是 pivot了
    return nums[k - 1]
  }
  return quicksort(0, nums.length - 1)
}

// console.log(findKthLargest([3, 3, 3, 1, 1, 1, 2, 1, 5, 6, 4], 1))

// let a = [6, 5, 4, 3, 2, 1]
// let k = 2
// console.log(findKthLargest(a, k))
// target = 5
//p
// [5,5,5,5,5,5,5,5,5,5,5,5,3,2,2,2,2,2,1,1,1,2,2,2]
//  k = 3;
// 问题 case
console.log(findKthLargest([5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 3, 2, 1], 3))

// 认真 审题 认真审题 ！！！ 是 第k个最大的元素  第k个最大元素 不是 第k大元素！！！
// 如果是 第k大元素 上面题解就不对

// 这个算法 有问题！！！！！！  k - 1 >= ol && k - 1 <= r 不能确定是 左区间  k - 1 <= r  k-1实际是偏小的
// 这个题解有问题，k - 1 >= ol && k - 1 <= r 不能确定目标值在左区间，因为当数组有很多重复元素的时候，实际目标值的下标肯定是要大于 k-1的，所以 k - 1 <= r 不能确定目标值在左区间。[5, 5, 5, 5, nums = [5, 5, 5, 5, 5, 5, 5, 3, 2, 1], k=3 这个case就不对
